package com.wrial.kind.tree;
/*
 * @Author  Wrial
 * @Date Created in 16:02 2020/8/23
 * @Description  二叉搜索树的第k大节点
 * 输入: root = [3,1,4,null,2], k = 1
       3
      / \
     1   4
      \
       2
    输出: 4
 */

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class KthLargest {
    /**
     * 传统方式，先序遍历，然后放到一个数组中，再倒着取
     */
//    public int kthLargest(TreeNode root, int k) {
//        if (root == null) return 0;
//        LinkedList<TreeNode> stack = new LinkedList<>();
//        List<Integer> ansList = new ArrayList<>();
//        while (root != null || !stack.isEmpty()) {
//            while (root != null) {
//                stack.push(root);
//                root = root.left;
//            }
//            root = stack.pop();
//            ansList.add(root.val);
//            root = root.right;
//        }
//        return ansList.get(ansList.size() - k);
//    }

    /**
     * 使用中序遍历的逆序   右  中  左   就可以完成从大到小的排列   左 中 右 是从小到大
     */
    public int kthLargest(TreeNode root, int k) {
        if (root==null) return 0;
        LinkedList<TreeNode> stack = new LinkedList<>();
        int count = 0;
        while (root!=null||!stack.isEmpty()){
            while (root!=null){
                stack.push(root);
                root = root.right;
            }
            root = stack.pop();
            count++;
            if (count==k){
                return root.val;
            }
            root = root.left;
        }
        return 0;
    }


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
